#include <iostream>
using namespace std;

#define MAX 20

int n, m, cost;
int w[MAX][MAX];  // 重量矩阵
int c[MAX][MAX];  // 价格矩阵
int select[MAX];  // 最终选择的最佳供应商
int x[MAX];       // 暂存的最佳供应商
bool bought[MAX]; // 记录供应商是否已经购买过
int ans = 0x7FFFFFFF, tmpw = 0, tmpc = 0;

// 为第k个零件选择供应商
void Choose(int k)
{
    int i;
    if (k > n) // 已经选好n个零件了，则结束
    {
        ans = tmpw;
        for (i = 1; i <= n; i++)
            select[i] = x[i];
    }
    else
    {
        for (i = 1; i <= m; i++)
        {
            if (!bought[i] && tmpc + c[k][i] <= cost && tmpw + w[k][i] < ans)
            {
                x[k] = i;
                tmpc += c[k][i];
                tmpw += w[k][i];
                bought[i] = true;
                Choose(k + 1);
                tmpc -= c[k][i];
                tmpw -= w[k][i];
                bought[i] = false;
            }
        }
    }
}

void Init()
{
    int i, j;
    cout << "请输入部件数，供应商数，限定价格：" << endl;
    cin >> n >> m >> cost;
    cout << "请输入W(i,j)：" << endl;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            cin >> w[i][j];
    cout << "请输入c(i,j)：" << endl;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            cin >> c[i][j];
}

int main()
{
    Init();
    Choose(1);
    cout << "最佳供应商选择：(每处最多购买一个零件)" << endl;
    for (int i = 1; i <= n; i++)
        cout << select[i] << ' ';
    cout << endl;

    cout << ans;
    return 0;
}

/*
请输入部件数，供应商数，限定价格：
3 3 7
请输入W(i,j)：
1 2 3
3 2 1
2 3 2
请输入c(i,j)：
1 2 3
5 4 2
2 1 2
最佳供应商选择：(每处最多购买一个零件)
1 2 3
5
*/